package course.p3_arraysSort.exa05_mergeSort;

import java.util.Arrays;

/**
 * 归并排序Java实现
 */
public class IntMergeSort {


    /**
     * 合并两个已经排好序的数组
     * @param a
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(int[] a, int left,int mid,int right) {

        int[] result = new int[right-left+1];

        // p1,p2是检测指针， index是存放指针
        int p1 = left, p2 = mid+1, index = 0;
        // 执行双数组元素比较
        while (p1<=mid&&p2<=right) {
            if(a[p1]<=a[p2]){
                result[index++] = a[p1++];
            }
            else{
                result[index++] = a[p2++];
            }
        }

        while (p1<=mid) result[index++] = a[p1++];
        while (p2<=right) result[index++] = a[p2++];

        System.arraycopy(result, 0, a, left, result.length);

    }

    /**
     * 归并排序，采用分治，递归思想
     * @param a
     * @param start
     * @param end
     */
    public static void mergeSort(int[] a,int start,int end) {
        if(start < end){
            int mid = (start+end)/2;
            mergeSort(a,start,mid);
            mergeSort(a,mid+1,end);
            merge(a,start,mid,end);
        }
    }

    public static void mergeSortTest() {
        int[] numbs = {24,13,26,1,2,27,38,15};
        mergeSort(numbs,0,numbs.length-1);
        System.out.println(Arrays.toString(numbs));
    }

    public static void main(String[] args) {
        mergeSortTest();
    }


}
